package lc.q250_300;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Q264 {

    public int nthUglyNumber(int n) {
        // 控制三个数组，和一个数
        // 指向2的数组,指向5的数组，指向3的数组
        int[] dp = new int[n + 1];
        dp[1] = 1;
        // dp(i)从何而来呢
        int p2 =1,p3 =1, p5 = 1;
        String s = "";
        for (int i = 2; i <= n; i++) {
            int num2 = dp[p2] * 2;
            int num3 = dp[p3] * 3;
            int num5 = dp[p5] * 5;
            dp[i] = Integer.min(num2, Integer.min(num3, num5));
            if (dp[i] == num2) {
                p2 ++;
            }
            if (dp[i] == num3) {
                p3 ++;
            }
            if (dp[i] == num5) {
                p5 ++;
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(new Q264().nthUglyNumber(10));
    }
}
